/*
 * Created by guoyh on Sat Dec 10 2022 20:59:11
 * leetcode NO.23 https://leetcode.cn/problems/merge-k-sorted-lists/
 * [1->4->5,
 * 1->3->4,
 * 2->6 ]
 * 1->1->2->3->4->4->5->6
 */

#include <iostream>
#include<queue>
#include <gtest/gtest.h>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

 
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<int, vector<int>, std::greater<int>> merged_data;
        for(ListNode* l : lists){
            while(l != nullptr){
                // cout<<"l-val="<<l->val<<endl;
                merged_data.push(l->val);
                l = l->next;
            }
        }
        // 尾插法创建链表
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while(!merged_data.empty()){
            ListNode* newNode = new ListNode(merged_data.top());
            merged_data.pop();
            newNode->next = nullptr;
            tail->next = newNode;
            tail = tail->next;
        }
        return head->next;
    }
};
ListNode* build_linklist(vector<int> v);
void print(ListNode* l);

TEST(MyTest, AddTest) {
    string line;
    vector<ListNode*> input;
    vector<int> v1 = {1,4,5};
    vector<int> v2 = {1,3,4};
    vector<int> v3 = {2,6};
    input.push_back(build_linklist(v1));
    input.push_back(build_linklist(v2));
    input.push_back(build_linklist(v3));

    Solution slu;

    ListNode* res = slu.mergeKLists(input);
    print(res);
    EXPECT_NE(res, nullptr);
}

// 尾插法创建链表
ListNode* build_linklist(vector<int> v){
    ListNode* dummy = new ListNode();
    ListNode* tail = dummy;
    for(int i : v){
        ListNode* newNode = new ListNode(i);
        newNode->next = nullptr;
        tail->next = newNode;
        tail = tail->next;
    }
    return dummy->next;
}


void print(ListNode* l){
    while(l){
        cout<<l->val<<",";
        l = l->next;
    }
    cout<<endl;
}

int main(int argc, char *argv[]) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}
